package com.tgy.algorithm.base._单调栈;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class _获取数组每一个位置最近的小于当前值_01 {

    public static int[][] getEachMin(int[] nums) {


        if (nums == null || nums.length == 0) {
            return null;
        }

        int len = nums.length;
        int[][] mins = new int[len][2];
        Stack<List<Integer>> stack = new Stack<>();
        int value;
        for (int i = 0; i < len; i++) {
            value = nums[i];
            while (!stack.isEmpty()) {
                List<Integer> topList = stack.peek();
                // 不满足条件，直接跳出循环
                if (!topList.isEmpty() && nums[topList.get(topList.size() - 1)] <= value) {
                    break;
                }

                stack.pop();
                for (Integer idx : topList) {
                    mins[idx][1] = i;
                    if (stack.isEmpty()) {
                        mins[idx][0] = -1;
                    }else {
                        List<Integer> curList = stack.peek();
                        mins[idx][0] = curList.get(curList.size() - 1);
                    }
                }
            }
            if (!stack.isEmpty() && nums[stack.peek().get(0)] == value) {
                List<Integer> topList = stack.peek();
                topList.add(i);
            }else {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(i);
                stack.push(list);
            }

        }

        while (!stack.isEmpty()) {
            List<Integer> topList = stack.pop();
            for (Integer i : topList) {
                mins[i][1] = -1;
                mins[i][0] = stack.isEmpty()?-1:stack.peek().get(stack.peek().size() - 1);
            }
        }

        return mins;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2,1,2,3,2,3,4,5,3};
        int[][] eachMin = getEachMin(nums);
        for (int i = 0; i < eachMin.length; i++) {
            int[] em = eachMin[i];
            String leftValue = em[0] == -1? "没有": ("左边:" +nums[em[0]] + " ");
            String rightValue = em[1] == -1? "没有": (" 右边:" + nums[em[1]]);
            System.out.println( nums[i] + " " + leftValue + " "+ rightValue);
        }
    }
}
